package com.heng.test;

import java.lang.String;

public class Graph {
    static class Node{
        int[] s = new int[2];//左右儿子
        int p;//父亲
        int v;//节点的权值
        int cnt;//权值出现的次数
        int size;//子树大小
        void init(int p1, int v1) {
            p = p1;
            v = v1;
            cnt = size = 1;
        }
    }

    static Node[] tr = new Node[10];

    static {
        for (int i = 0; i < 10; i++) {
            tr[i] = new Node();
        }
    }
    static int root;//根节点的编号
    static int idx;//节点的个数

    static void pushup(int x) {
        tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size+tr[x].cnt;
    }

    static void rotate(int x) {
        int y = tr[x].p;
        int z = tr[y].p;
        int k = tr[y].s[1] == x ? 1 : 0;
        tr[y].s[k] = tr[x].s[k^1];
        tr[tr[x].s[k^1]].p = y;
        tr[x].s[k^1] = y;
        tr[y].p = x;
        tr[z].s[tr[z].s[1]==y ? 1:0] = x;
        tr[x].p=z;
        pushup(y);
        pushup(x);
    }

    static void splay(int x, int k) {
        while (tr[x].p!=k) {
            int y = tr[x].p;
            int z = tr[y].p;
            if (z!=k) {
                if (((tr[y].s[0] == x ? 1 : 0) ^ (tr[z].s[0] == y ? 1 : 0)) > 0) {
                    rotate(x);
                } else {
                    rotate(y);
                }
            }
            rotate(x);
        }
        if(k == 0) root = x;
    }

    static void find(int v) {
        int x = root;
        while (tr[x].s[v>tr[x].v ? 1:0] != 0 && v!=tr[x].v)
            x = tr[x].s[v>tr[x].v?1:0];
        splay(x,0);
    }

    static int get_pre(int v) {
        find(v);
        int x = root;
        if (tr[x].v < v) return x;
        x = tr[x].s[0];
        while (tr[x].s[1] != 0) x = tr[x].s[1];
        return x;
    }

    static int get_suc(int v) {
        find(v);
        int x = root;
        if (tr[x].v>v) return x;
        x=tr[x].s[1];
        while (tr[x].s[0]!=0)x=tr[x].s[0];
        return x;
    }

    static void del(int v) {
        int pre=get_pre(v);
        int suc=get_suc(v);
        splay(pre,0);
        splay(suc,pre);
        int del = tr[suc].s[0];
        if(tr[del].cnt>1){
            tr[del].cnt--;
            splay(del,0);
        } else {
            tr[suc].s[0]=0;
            splay(suc,0);
        }
    }

    static int get_rank(int v) {
        find(v);
        return tr[tr[root].s[0]].size;
    }

    static int get_val(int k) {
        int x=root;
        while (true) {
            int y = tr[x].s[0];
            if(tr[y].size+tr[x].cnt<k) {
                k-=tr[y].size+tr[x].cnt;
                x=tr[x].s[1];
            } else {
                if(tr[y].size>=k)x=tr[x].s[0];
                else break;
            }
        }
        splay(x,0);
        return tr[x].v;
    }

    static void insert(int v) {
        int x = root;
        int p = 0;
        while (x != 0 && tr[x].v != v) {
            p = x;
            x = tr[x].s[v > tr[x].v ? 1 : 0];
        }
        if (x != 0) tr[x].cnt++;
        else {
            x = ++idx;
            tr[p].s[v > tr[p].v ? 1 : 0] = x;
            tr[x].init(p, v);
        }
        splay(x,0);
    }

    public static void main(String[] args) {
        insert((int) -1e9);
        insert((int) 1e9);
        insert(1);
        insert(5);
        insert(8);
        insert(6);
        insert(9);
        insert(2);
        System.out.println(tr[root].s[1]);
    }
}
